package com.woniu.Test;

/**
 * 判断链表是否有环，且找出环的入口的测试类
 *
 * @author WenXin
 * @version 1.0
 * @description: TODO
 * @date 2022/8/27 14:46
 */
public class CircularLinkedTest {
    public static void main(String[] args) {
        //自定义模拟一个环形链表
        Node node1 = new Node(1, "node1");
        Node node2 = new Node(2, "node2");
        Node node3 = new Node(3, "node3");
        Node node4 = new Node(4, "node4");
        Node node5 = new Node(5, "node5");
        //连接节点
        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
        //让链表node5指向node3形成环
        node5.setNext(node3);
        //问题一：判断以上链表中是否存在环
        boolean result = false;//fales为不存在，true为存在
        //解决方案：快慢指针，index1移动1次，index移动2次，如果两个指针相遇 则证明有环
        Node index1 = node1;
        Node index2 = node1;
        while (true) {
            if (index1.getNext() == null || index2.getNext().getNext() == null) {
                break;
            } else {
                if (index1.getNext() != index2.getNext().getNext()) {
                    index1 = index1.getNext();
                    index2 = index2.getNext().getNext();
                } else {
                    result = true;
                    break;
                }
            }
        }
        System.out.println("是否存在环：" + result);//fales为不存在，true为存在
        //问题二：当存在环，找出环的交点，用于解开环。
        //解题思路分析------------------------------------------------
        //经过推导，能得到环的长度 = 起点到环的交点 + 交点到两个快慢指针的交点距离
        /*也就是  H = L + x, 求交点的关键就是，当两个指针速度一样，当一个指针从交点处开始走，
        ，交点处的距离正好为L + X 也就是让第一个指针先走一个环的距离。第二个指针同时从起点开始走，
        那么两者相遇时，就是环的入口*/
        //先求环的长度：通过节点的属性  NodeNum  算出节点的个数，从而求出环的长度
        //解题思路分析------------------------------------------------


        //最上面的循环结束后，找到了相遇点。相遇点一定在环上面，因此先获取相遇点：
        int Count = 0;//用于环的节点个数
        Node index3 = index1;//此为交点，
        while (true) {
            Count++;
            if (index3.getNext() == index1) {
                break;
            } else {
                index3 = index3.getNext();

            }
        }
        System.out.println("环的节点个数为：" + Count);
        //定义一个节点让他先走一个环的距离
        Node index4 = node1;
        //循环结束后，index4移动了一个环的距离
        for (int i = 0; i < Count; i++) {
            index4 = index4.getNext();
        }
        Node index5 = node1;//此时再让该节点从起点出发，那么与index4相遇点就是环的入口
        while (true) {
            if (index5.getNext() == index4.getNext()) {
                break;
            } else {
                index5 = index5.getNext();
                index4 = index4.getNext();
            }
        }
        System.out.println("环的入口节点名为：" + index5.getNext().getNodeName());
    }
}
